void Delay(int us){
//	sceKernelDelayThread(us);
}

/* fix_fft.c - Fixed-point in-place Fast Fourier Transform  */
/*
  All data are fixed-point short integers, in which -32768
  to +32768 represent -1.0 to +1.0 respectively. Integer
  arithmetic is used for speed, instead of the more natural
  floating-point.

  For the forward FFT (time -> freq), fixed scaling is
  performed to prevent arithmetic overflow, and to map a 0dB
  sine/cosine wave (i.e. amplitude = 32767) to two -6dB freq
  coefficients. The return value is always 0.

  For the inverse FFT (freq -> time), fixed scaling cannot be
  done, as two 0dB coefficients would sum to a peak amplitude
  of 64K, overflowing the 32k range of the fixed-point integers.
  Thus, the fix_fft() routine performs variable scaling, and
  returns a value which is the number of bits LEFT by which
  the output must be shifted to get the actual amplitude
  (i.e. if fix_fft() returns 3, each value of fr[] and fi[]
  must be multiplied by 8 (2**3) for proper scaling.
  Clearly, this cannot be done within fixed-point short
  integers. In practice, if the result is to be used as a
  filter, the scale_shift can usually be ignored, as the
  result will be approximately correctly normalized as is.

  Written by:  Tom Roberts  11/8/89
  Made portable:  Malcolm Slaney 12/15/94 malcolm@interval.com
  Enhanced:  Dimitrios P. Bouras  14 Jun 2006 dbouras@ieee.org
*/

/*
  Henceforth "short" implies 16-bit word. If this is not
  the case in your architecture, please replace "short"
  with a type definition which *is* a 16-bit word.
*/

/*
  Since we only use 3/4 of N_WAVE, we define only
  this many samples, in order to conserve data space.
*/
/*
#define N_WAVE      1024    // full length of Sinewave[]
#define LOG2_N_WAVE 10      // log2(N_WAVE)
short Sinewave[N_WAVE-N_WAVE/4] = {
      0,    201,    402,    603,    804,   1005,   1206,   1406,
   1607,   1808,   2009,   2209,   2410,   2610,   2811,   3011,
   3211,   3411,   3611,   3811,   4011,   4210,   4409,   4608,
   4807,   5006,   5205,   5403,   5601,   5799,   5997,   6195,
   6392,   6589,   6786,   6982,   7179,   7375,   7571,   7766,
   7961,   8156,   8351,   8545,   8739,   8932,   9126,   9319,
   9511,   9703,   9895,  10087,  10278,  10469,  10659,  10849,
  11038,  11227,  11416,  11604,  11792,  11980,  12166,  12353,
  12539,  12724,  12909,  13094,  13278,  13462,  13645,  13827,
  14009,  14191,  14372,  14552,  14732,  14911,  15090,  15268,
  15446,  15623,  15799,  15975,  16150,  16325,  16499,  16672,
  16845,  17017,  17189,  17360,  17530,  17699,  17868,  18036,
  18204,  18371,  18537,  18702,  18867,  19031,  19194,  19357,
  19519,  19680,  19840,  20000,  20159,  20317,  20474,  20631,
  20787,  20942,  21096,  21249,  21402,  21554,  21705,  21855,
  22004,  22153,  22301,  22448,  22594,  22739,  22883,  23027,
  23169,  23311,  23452,  23592,  23731,  23869,  24006,  24143,
  24278,  24413,  24546,  24679,  24811,  24942,  25072,  25201,
  25329,  25456,  25582,  25707,  25831,  25954,  26077,  26198,
  26318,  26437,  26556,  26673,  26789,  26905,  27019,  27132,
  27244,  27355,  27466,  27575,  27683,  27790,  27896,  28001,
  28105,  28208,  28309,  28410,  28510,  28608,  28706,  28802,
  28897,  28992,  29085,  29177,  29268,  29358,  29446,  29534,
  29621,  29706,  29790,  29873,  29955,  30036,  30116,  30195,
  30272,  30349,  30424,  30498,  30571,  30643,  30713,  30783,
  30851,  30918,  30984,  31049,  31113,  31175,  31236,  31297,
  31356,  31413,  31470,  31525,  31580,  31633,  31684,  31735,
  31785,  31833,  31880,  31926,  31970,  32014,  32056,  32097,
  32137,  32176,  32213,  32249,  32284,  32318,  32350,  32382,
  32412,  32441,  32468,  32495,  32520,  32544,  32567,  32588,
  32609,  32628,  32646,  32662,  32678,  32692,  32705,  32717,
  32727,  32736,  32744,  32751,  32757,  32761,  32764,  32766,
  32767,  32766,  32764,  32761,  32757,  32751,  32744,  32736,
  32727,  32717,  32705,  32692,  32678,  32662,  32646,  32628,
  32609,  32588,  32567,  32544,  32520,  32495,  32468,  32441,
  32412,  32382,  32350,  32318,  32284,  32249,  32213,  32176,
  32137,  32097,  32056,  32014,  31970,  31926,  31880,  31833,
  31785,  31735,  31684,  31633,  31580,  31525,  31470,  31413,
  31356,  31297,  31236,  31175,  31113,  31049,  30984,  30918,
  30851,  30783,  30713,  30643,  30571,  30498,  30424,  30349,
  30272,  30195,  30116,  30036,  29955,  29873,  29790,  29706,
  29621,  29534,  29446,  29358,  29268,  29177,  29085,  28992,
  28897,  28802,  28706,  28608,  28510,  28410,  28309,  28208,
  28105,  28001,  27896,  27790,  27683,  27575,  27466,  27355,
  27244,  27132,  27019,  26905,  26789,  26673,  26556,  26437,
  26318,  26198,  26077,  25954,  25831,  25707,  25582,  25456,
  25329,  25201,  25072,  24942,  24811,  24679,  24546,  24413,
  24278,  24143,  24006,  23869,  23731,  23592,  23452,  23311,
  23169,  23027,  22883,  22739,  22594,  22448,  22301,  22153,
  22004,  21855,  21705,  21554,  21402,  21249,  21096,  20942,
  20787,  20631,  20474,  20317,  20159,  20000,  19840,  19680,
  19519,  19357,  19194,  19031,  18867,  18702,  18537,  18371,
  18204,  18036,  17868,  17699,  17530,  17360,  17189,  17017,
  16845,  16672,  16499,  16325,  16150,  15975,  15799,  15623,
  15446,  15268,  15090,  14911,  14732,  14552,  14372,  14191,
  14009,  13827,  13645,  13462,  13278,  13094,  12909,  12724,
  12539,  12353,  12166,  11980,  11792,  11604,  11416,  11227,
  11038,  10849,  10659,  10469,  10278,  10087,   9895,   9703,
   9511,   9319,   9126,   8932,   8739,   8545,   8351,   8156,
   7961,   7766,   7571,   7375,   7179,   6982,   6786,   6589,
   6392,   6195,   5997,   5799,   5601,   5403,   5205,   5006,
   4807,   4608,   4409,   4210,   4011,   3811,   3611,   3411,
   3211,   3011,   2811,   2610,   2410,   2209,   2009,   1808,
   1607,   1406,   1206,   1005,    804,    603,    402,    201,
      0,   -201,   -402,   -603,   -804,  -1005,  -1206,  -1406,
  -1607,  -1808,  -2009,  -2209,  -2410,  -2610,  -2811,  -3011,
  -3211,  -3411,  -3611,  -3811,  -4011,  -4210,  -4409,  -4608,
  -4807,  -5006,  -5205,  -5403,  -5601,  -5799,  -5997,  -6195,
  -6392,  -6589,  -6786,  -6982,  -7179,  -7375,  -7571,  -7766,
  -7961,  -8156,  -8351,  -8545,  -8739,  -8932,  -9126,  -9319,
  -9511,  -9703,  -9895, -10087, -10278, -10469, -10659, -10849,
 -11038, -11227, -11416, -11604, -11792, -11980, -12166, -12353,
 -12539, -12724, -12909, -13094, -13278, -13462, -13645, -13827,
 -14009, -14191, -14372, -14552, -14732, -14911, -15090, -15268,
 -15446, -15623, -15799, -15975, -16150, -16325, -16499, -16672,
 -16845, -17017, -17189, -17360, -17530, -17699, -17868, -18036,
 -18204, -18371, -18537, -18702, -18867, -19031, -19194, -19357,
 -19519, -19680, -19840, -20000, -20159, -20317, -20474, -20631,
 -20787, -20942, -21096, -21249, -21402, -21554, -21705, -21855,
 -22004, -22153, -22301, -22448, -22594, -22739, -22883, -23027,
 -23169, -23311, -23452, -23592, -23731, -23869, -24006, -24143,
 -24278, -24413, -24546, -24679, -24811, -24942, -25072, -25201,
 -25329, -25456, -25582, -25707, -25831, -25954, -26077, -26198,
 -26318, -26437, -26556, -26673, -26789, -26905, -27019, -27132,
 -27244, -27355, -27466, -27575, -27683, -27790, -27896, -28001,
 -28105, -28208, -28309, -28410, -28510, -28608, -28706, -28802,
 -28897, -28992, -29085, -29177, -29268, -29358, -29446, -29534,
 -29621, -29706, -29790, -29873, -29955, -30036, -30116, -30195,
 -30272, -30349, -30424, -30498, -30571, -30643, -30713, -30783,
 -30851, -30918, -30984, -31049, -31113, -31175, -31236, -31297,
 -31356, -31413, -31470, -31525, -31580, -31633, -31684, -31735,
 -31785, -31833, -31880, -31926, -31970, -32014, -32056, -32097,
 -32137, -32176, -32213, -32249, -32284, -32318, -32350, -32382,
 -32412, -32441, -32468, -32495, -32520, -32544, -32567, -32588,
 -32609, -32628, -32646, -32662, -32678, -32692, -32705, -32717,
 -32727, -32736, -32744, -32751, -32757, -32761, -32764, -32766,
};
*/

#define N_WAVE      2048    // full length of Sinewave[]
#define LOG2_N_WAVE 11      // log2(N_WAVE)
short Sinewave[N_WAVE-N_WAVE/4] = {
      0,    100,    201,    301,    402,    502,    603,    703,
    804,    904,   1005,   1105,   1206,   1306,   1406,   1507,
   1607,   1708,   1808,   1908,   2009,   2109,   2209,   2310,
   2410,   2510,   2610,   2711,   2811,   2911,   3011,   3111,
   3211,   3311,   3411,   3511,   3611,   3711,   3811,   3911,
   4011,   4110,   4210,   4310,   4409,   4509,   4608,   4708,
   4807,   4907,   5006,   5106,   5205,   5304,   5403,   5502,
   5601,   5700,   5799,   5898,   5997,   6096,   6195,   6293,
   6392,   6491,   6589,   6688,   6786,   6884,   6982,   7081,
   7179,   7277,   7375,   7473,   7571,   7668,   7766,   7864,
   7961,   8059,   8156,   8253,   8351,   8448,   8545,   8642,
   8739,   8836,   8932,   9029,   9126,   9222,   9319,   9415,
   9511,   9607,   9703,   9799,   9895,   9991,  10087,  10182,
  10278,  10373,  10469,  10564,  10659,  10754,  10849,  10944,
  11038,  11133,  11227,  11322,  11416,  11510,  11604,  11698,
  11792,  11886,  11980,  12073,  12166,  12260,  12353,  12446,
  12539,  12632,  12724,  12817,  12909,  13002,  13094,  13186,
  13278,  13370,  13462,  13553,  13645,  13736,  13827,  13918,
  14009,  14100,  14191,  14281,  14372,  14462,  14552,  14642,
  14732,  14822,  14911,  15001,  15090,  15179,  15268,  15357,
  15446,  15534,  15623,  15711,  15799,  15887,  15975,  16063,
  16150,  16238,  16325,  16412,  16499,  16586,  16672,  16759,
  16845,  16931,  17017,  17103,  17189,  17274,  17360,  17445,
  17530,  17615,  17699,  17784,  17868,  17952,  18036,  18120,
  18204,  18287,  18371,  18454,  18537,  18620,  18702,  18785,
  18867,  18949,  19031,  19113,  19194,  19276,  19357,  19438,
  19519,  19599,  19680,  19760,  19840,  19920,  20000,  20079,
  20159,  20238,  20317,  20396,  20474,  20553,  20631,  20709,
  20787,  20864,  20942,  21019,  21096,  21173,  21249,  21326,
  21402,  21478,  21554,  21629,  21705,  21780,  21855,  21930,
  22004,  22079,  22153,  22227,  22301,  22374,  22448,  22521,
  22594,  22666,  22739,  22811,  22883,  22955,  23027,  23098,
  23169,  23240,  23311,  23382,  23452,  23522,  23592,  23661,
  23731,  23800,  23869,  23938,  24006,  24075,  24143,  24211,
  24278,  24346,  24413,  24480,  24546,  24613,  24679,  24745,
  24811,  24877,  24942,  25007,  25072,  25136,  25201,  25265,
  25329,  25392,  25456,  25519,  25582,  25645,  25707,  25769,
  25831,  25893,  25954,  26016,  26077,  26137,  26198,  26258,
  26318,  26378,  26437,  26497,  26556,  26615,  26673,  26731,
  26789,  26847,  26905,  26962,  27019,  27076,  27132,  27188,
  27244,  27300,  27355,  27411,  27466,  27520,  27575,  27629,
  27683,  27736,  27790,  27843,  27896,  27948,  28001,  28053,
  28105,  28156,  28208,  28259,  28309,  28360,  28410,  28460,
  28510,  28559,  28608,  28657,  28706,  28754,  28802,  28850,
  28897,  28945,  28992,  29038,  29085,  29131,  29177,  29222,
  29268,  29313,  29358,  29402,  29446,  29490,  29534,  29577,
  29621,  29663,  29706,  29748,  29790,  29832,  29873,  29915,
  29955,  29996,  30036,  30076,  30116,  30156,  30195,  30234,
  30272,  30311,  30349,  30386,  30424,  30461,  30498,  30535,
  30571,  30607,  30643,  30678,  30713,  30748,  30783,  30817,
  30851,  30885,  30918,  30951,  30984,  31017,  31049,  31081,
  31113,  31144,  31175,  31206,  31236,  31267,  31297,  31326,
  31356,  31385,  31413,  31442,  31470,  31498,  31525,  31553,
  31580,  31606,  31633,  31659,  31684,  31710,  31735,  31760,
  31785,  31809,  31833,  31856,  31880,  31903,  31926,  31948,
  31970,  31992,  32014,  32035,  32056,  32077,  32097,  32117,
  32137,  32156,  32176,  32194,  32213,  32231,  32249,  32267,
  32284,  32301,  32318,  32334,  32350,  32366,  32382,  32397,
  32412,  32426,  32441,  32455,  32468,  32482,  32495,  32508,
  32520,  32532,  32544,  32556,  32567,  32578,  32588,  32599,
  32609,  32618,  32628,  32637,  32646,  32654,  32662,  32670,
  32678,  32685,  32692,  32699,  32705,  32711,  32717,  32722,
  32727,  32732,  32736,  32740,  32744,  32748,  32751,  32754,
  32757,  32759,  32761,  32763,  32764,  32765,  32766,  32766,
  32767,  32766,  32766,  32765,  32764,  32763,  32761,  32759,
  32757,  32754,  32751,  32748,  32744,  32740,  32736,  32732,
  32727,  32722,  32717,  32711,  32705,  32699,  32692,  32685,
  32678,  32670,  32662,  32654,  32646,  32637,  32628,  32618,
  32609,  32599,  32588,  32578,  32567,  32556,  32544,  32532,
  32520,  32508,  32495,  32482,  32468,  32455,  32441,  32426,
  32412,  32397,  32382,  32366,  32350,  32334,  32318,  32301,
  32284,  32267,  32249,  32231,  32213,  32194,  32176,  32156,
  32137,  32117,  32097,  32077,  32056,  32035,  32014,  31992,
  31970,  31948,  31926,  31903,  31880,  31856,  31833,  31809,
  31785,  31760,  31735,  31710,  31684,  31659,  31633,  31606,
  31580,  31553,  31525,  31498,  31470,  31442,  31413,  31385,
  31356,  31326,  31297,  31267,  31236,  31206,  31175,  31144,
  31113,  31081,  31049,  31017,  30984,  30951,  30918,  30885,
  30851,  30817,  30783,  30748,  30713,  30678,  30643,  30607,
  30571,  30535,  30498,  30461,  30424,  30386,  30349,  30311,
  30272,  30234,  30195,  30156,  30116,  30076,  30036,  29996,
  29955,  29915,  29873,  29832,  29790,  29748,  29706,  29663,
  29621,  29577,  29534,  29490,  29446,  29402,  29358,  29313,
  29268,  29222,  29177,  29131,  29085,  29038,  28992,  28945,
  28897,  28850,  28802,  28754,  28706,  28657,  28608,  28559,
  28510,  28460,  28410,  28360,  28309,  28259,  28208,  28156,
  28105,  28053,  28001,  27948,  27896,  27843,  27790,  27736,
  27683,  27629,  27575,  27520,  27466,  27411,  27355,  27300,
  27244,  27188,  27132,  27076,  27019,  26962,  26905,  26847,
  26789,  26731,  26673,  26615,  26556,  26497,  26437,  26378,
  26318,  26258,  26198,  26137,  26077,  26016,  25954,  25893,
  25831,  25769,  25707,  25645,  25582,  25519,  25456,  25392,
  25329,  25265,  25201,  25136,  25072,  25007,  24942,  24877,
  24811,  24745,  24679,  24613,  24546,  24480,  24413,  24346,
  24278,  24211,  24143,  24075,  24006,  23938,  23869,  23800,
  23731,  23661,  23592,  23522,  23452,  23382,  23311,  23240,
  23169,  23098,  23027,  22955,  22883,  22811,  22739,  22666,
  22594,  22521,  22448,  22374,  22301,  22227,  22153,  22079,
  22004,  21930,  21855,  21780,  21705,  21629,  21554,  21478,
  21402,  21326,  21249,  21173,  21096,  21019,  20942,  20864,
  20787,  20709,  20631,  20553,  20474,  20396,  20317,  20238,
  20159,  20079,  20000,  19920,  19840,  19760,  19680,  19599,
  19519,  19438,  19357,  19276,  19194,  19113,  19031,  18949,
  18867,  18785,  18702,  18620,  18537,  18454,  18371,  18287,
  18204,  18120,  18036,  17952,  17868,  17784,  17699,  17615,
  17530,  17445,  17360,  17274,  17189,  17103,  17017,  16931,
  16845,  16759,  16672,  16586,  16499,  16412,  16325,  16238,
  16150,  16063,  15975,  15887,  15799,  15711,  15623,  15534,
  15446,  15357,  15268,  15179,  15090,  15001,  14911,  14822,
  14732,  14642,  14552,  14462,  14372,  14281,  14191,  14100,
  14009,  13918,  13827,  13736,  13645,  13553,  13462,  13370,
  13278,  13186,  13094,  13002,  12909,  12817,  12724,  12632,
  12539,  12446,  12353,  12260,  12166,  12073,  11980,  11886,
  11792,  11698,  11604,  11510,  11416,  11322,  11227,  11133,
  11038,  10944,  10849,  10754,  10659,  10564,  10469,  10373,
  10278,  10182,  10087,   9991,   9895,   9799,   9703,   9607,
   9511,   9415,   9319,   9222,   9126,   9029,   8932,   8836,
   8739,   8642,   8545,   8448,   8351,   8253,   8156,   8059,
   7961,   7864,   7766,   7668,   7571,   7473,   7375,   7277,
   7179,   7081,   6982,   6884,   6786,   6688,   6589,   6491,
   6392,   6293,   6195,   6096,   5997,   5898,   5799,   5700,
   5601,   5502,   5403,   5304,   5205,   5106,   5006,   4907,
   4807,   4708,   4608,   4509,   4409,   4310,   4210,   4110,
   4011,   3911,   3811,   3711,   3611,   3511,   3411,   3311,
   3211,   3111,   3011,   2911,   2811,   2711,   2610,   2510,
   2410,   2310,   2209,   2109,   2009,   1908,   1808,   1708,
   1607,   1507,   1406,   1306,   1206,   1105,   1005,    904,
    804,    703,    603,    502,    402,    301,    201,    100,
      0,   -100,   -201,   -301,   -402,   -502,   -603,   -703,
   -804,   -904,  -1005,  -1105,  -1206,  -1306,  -1406,  -1507,
  -1607,  -1708,  -1808,  -1908,  -2009,  -2109,  -2209,  -2310,
  -2410,  -2510,  -2610,  -2711,  -2811,  -2911,  -3011,  -3111,
  -3211,  -3311,  -3411,  -3511,  -3611,  -3711,  -3811,  -3911,
  -4011,  -4110,  -4210,  -4310,  -4409,  -4509,  -4608,  -4708,
  -4807,  -4907,  -5006,  -5106,  -5205,  -5304,  -5403,  -5502,
  -5601,  -5700,  -5799,  -5898,  -5997,  -6096,  -6195,  -6293,
  -6392,  -6491,  -6589,  -6688,  -6786,  -6884,  -6982,  -7081,
  -7179,  -7277,  -7375,  -7473,  -7571,  -7668,  -7766,  -7864,
  -7961,  -8059,  -8156,  -8253,  -8351,  -8448,  -8545,  -8642,
  -8739,  -8836,  -8932,  -9029,  -9126,  -9222,  -9319,  -9415,
  -9511,  -9607,  -9703,  -9799,  -9895,  -9991, -10087, -10182,
 -10278, -10373, -10469, -10564, -10659, -10754, -10849, -10944,
 -11038, -11133, -11227, -11322, -11416, -11510, -11604, -11698,
 -11792, -11886, -11980, -12073, -12166, -12260, -12353, -12446,
 -12539, -12632, -12724, -12817, -12909, -13002, -13094, -13186,
 -13278, -13370, -13462, -13553, -13645, -13736, -13827, -13918,
 -14009, -14100, -14191, -14281, -14372, -14462, -14552, -14642,
 -14732, -14822, -14911, -15001, -15090, -15179, -15268, -15357,
 -15446, -15534, -15623, -15711, -15799, -15887, -15975, -16063,
 -16150, -16238, -16325, -16412, -16499, -16586, -16672, -16759,
 -16845, -16931, -17017, -17103, -17189, -17274, -17360, -17445,
 -17530, -17615, -17699, -17784, -17868, -17952, -18036, -18120,
 -18204, -18287, -18371, -18454, -18537, -18620, -18702, -18785,
 -18867, -18949, -19031, -19113, -19194, -19276, -19357, -19438,
 -19519, -19599, -19680, -19760, -19840, -19920, -20000, -20079,
 -20159, -20238, -20317, -20396, -20474, -20553, -20631, -20709,
 -20787, -20864, -20942, -21019, -21096, -21173, -21249, -21326,
 -21402, -21478, -21554, -21629, -21705, -21780, -21855, -21930,
 -22004, -22079, -22153, -22227, -22301, -22374, -22448, -22521,
 -22594, -22666, -22739, -22811, -22883, -22955, -23027, -23098,
 -23169, -23240, -23311, -23382, -23452, -23522, -23592, -23661,
 -23731, -23800, -23869, -23938, -24006, -24075, -24143, -24211,
 -24278, -24346, -24413, -24480, -24546, -24613, -24679, -24745,
 -24811, -24877, -24942, -25007, -25072, -25136, -25201, -25265,
 -25329, -25392, -25456, -25519, -25582, -25645, -25707, -25769,
 -25831, -25893, -25954, -26016, -26077, -26137, -26198, -26258,
 -26318, -26378, -26437, -26497, -26556, -26615, -26673, -26731,
 -26789, -26847, -26905, -26962, -27019, -27076, -27132, -27188,
 -27244, -27300, -27355, -27411, -27466, -27520, -27575, -27629,
 -27683, -27736, -27790, -27843, -27896, -27948, -28001, -28053,
 -28105, -28156, -28208, -28259, -28309, -28360, -28410, -28460,
 -28510, -28559, -28608, -28657, -28706, -28754, -28802, -28850,
 -28897, -28945, -28992, -29038, -29085, -29131, -29177, -29222,
 -29268, -29313, -29358, -29402, -29446, -29490, -29534, -29577,
 -29621, -29663, -29706, -29748, -29790, -29832, -29873, -29915,
 -29955, -29996, -30036, -30076, -30116, -30156, -30195, -30234,
 -30272, -30311, -30349, -30386, -30424, -30461, -30498, -30535,
 -30571, -30607, -30643, -30678, -30713, -30748, -30783, -30817,
 -30851, -30885, -30918, -30951, -30984, -31017, -31049, -31081,
 -31113, -31144, -31175, -31206, -31236, -31267, -31297, -31326,
 -31356, -31385, -31413, -31442, -31470, -31498, -31525, -31553,
 -31580, -31606, -31633, -31659, -31684, -31710, -31735, -31760,
 -31785, -31809, -31833, -31856, -31880, -31903, -31926, -31948,
 -31970, -31992, -32014, -32035, -32056, -32077, -32097, -32117,
 -32137, -32156, -32176, -32194, -32213, -32231, -32249, -32267,
 -32284, -32301, -32318, -32334, -32350, -32366, -32382, -32397,
 -32412, -32426, -32441, -32455, -32468, -32482, -32495, -32508,
 -32520, -32532, -32544, -32556, -32567, -32578, -32588, -32599,
 -32609, -32618, -32628, -32637, -32646, -32654, -32662, -32670,
 -32678, -32685, -32692, -32699, -32705, -32711, -32717, -32722,
 -32727, -32732, -32736, -32740, -32744, -32748, -32751, -32754,
 -32757, -32759, -32761, -32763, -32764, -32765, -32766, -32766,
};


/*
  FIX_MPY() - fixed-point multiplication & scaling.
  Substitute inline assembly for hardware-specific
  optimization suited to a particluar DSP processor.
  Scaling ensures that result remains 16-bit.
*/
inline short FIX_MPY(short a, short b)
{
	// shift right one less bit (i.e. 15-1)
	int c = ((int)a * (int)b) >> 14;
	// last bit shifted out = rounding-bit
	b = c & 0x01;
	// last shift + rounding bit
	a = (c >> 1) + b;

	return a;
}

/*
  fix_fft() - perform forward/inverse fast Fourier transform.
  fr[n],fi[n] are real and imaginary arrays, both INPUT AND
  RESULT (in-place FFT), with 0 <= n < 2**m; set inverse to
  0 for forward transform (FFT), or 1 for iFFT.
*/
int fix_fft(short fr[], short fi[], short m, short inverse)
{
	int mr, nn, i, j, l, k, istep, n, scale, shift;
	short qr, qi, tr, ti, wr, wi;

	n = 1 << m;

	/* max FFT size = N_WAVE */
	if (n > N_WAVE)
		return -1;

	mr = 0;
	nn = n - 1;
	scale = 0;

	/* decimation in time - re-order data */
	for (m=1; m<=nn; ++m) {
		Delay(10);
		l = n;
		do {
			l >>= 1;
		} while (mr+l > nn);
		mr = (mr & (l-1)) + l;

		if (mr <= m)
			continue;
		tr = fr[m];
		fr[m] = fr[mr];
		fr[mr] = tr;
		ti = fi[m];
		fi[m] = fi[mr];
		fi[mr] = ti;
	}

	l = 1;
	k = LOG2_N_WAVE-1;
	while (l < n) {
		Delay(10);
		if (inverse) {
			/* variable scaling, depending upon data */
			shift = 0;
			for (i=0; i<n; ++i) {
				j = fr[i];
				if (j < 0)
					j = -j;
				m = fi[i];
				if (m < 0)
					m = -m;
				if (j > 16383 || m > 16383) {
					shift = 1;
					break;
				}
			}
			if (shift)
				++scale;
		} else {
			/*
			  fixed scaling, for proper normalization --
			  there will be log2(n) passes, so this results
			  in an overall factor of 1/n, distributed to
			  maximize arithmetic accuracy.
			*/
			shift = 1;
		}
		/*
		  it may not be obvious, but the shift will be
		  performed on each data point exactly once,
		  during this pass.
		*/
		istep = l << 1;
		for (m=0; m<l; ++m) {
			Delay(10);
			j = m << k;
			/* 0 <= j < N_WAVE/2 */
			wr =  Sinewave[j+N_WAVE/4];
			wi = -Sinewave[j];
			if (inverse)
				wi = -wi;
			if (shift) {
				wr >>= 1;
				wi >>= 1;
			}
			for (i=m; i<n; i+=istep) {
				Delay(10);
				j = i + l;
				tr = FIX_MPY(wr,fr[j]) - FIX_MPY(wi,fi[j]);
				ti = FIX_MPY(wr,fi[j]) + FIX_MPY(wi,fr[j]);
				qr = fr[i];
				qi = fi[i];
				if (shift) {
					qr >>= 1;
					qi >>= 1;
				}
				fr[j] = qr - tr;
				fi[j] = qi - ti;
				fr[i] = qr + tr;
				fi[i] = qi + ti;
			}
		}
		--k;
		l = istep;
	}
	return scale;
}

/*
  fix_fftr() - forward/inverse FFT on array of real numbers.
  Real FFT/iFFT using half-size complex FFT by distributing
  even/odd samples into real/imaginary arrays respectively.
  In order to save data space (i.e. to avoid two arrays, one
  for real, one for imaginary samples), we proceed in the
  following two steps: a) samples are rearranged in the real
  array so that all even samples are in places 0-(N/2-1) and
  all imaginary samples in places (N/2)-(N-1), and b) fix_fft
  is called with fr and fi pointing to index 0 and index N/2
  respectively in the original array. The above guarantees
  that fix_fft "sees" consecutive real samples as alternating
  real and imaginary samples in the complex array.
*/
int fix_fftr(short f[], int m, int inverse)
{
	int i, N = 1<<(m-1), scale = 0;
	short tt, *fr=f, *fi=&f[N];

	if (inverse)
		scale = fix_fft(fi, fr, m-1, inverse);
	for (i=1; i<N; i+=2) {
		tt = f[N+i-1];
		f[N+i-1] = f[i];
		f[i] = tt;
	}
	if (! inverse)
		scale = fix_fft(fi, fr, m-1, inverse);
	return scale;
}

